package org.leetcode.hard.leetcode23;

import org.algorithm.List.ListNode;

public class Solution {


    public ListNode mergeKLists2(ListNode[] lists){

        ListNode ans = null;

        for (int i = 0; i < lists.length; i++) {
           ans = mergeTwoLists2(ans,lists[i]);
        }
        return ans;
    }

    private ListNode mergeTwoLists2(ListNode list1,ListNode list2){
        if (list1==null || list2==null){
            return list1==null ?list2:list1;
        }

        ListNode dummy = new ListNode(0);
        ListNode merged = dummy;

        while (list1!=null && list2!=null){
            if (list1.val<list2.val){
                merged.next=list1;
                list1=list1.next;
            }else {
                merged.next=list2;
                list2= list2.next;
            }
            merged=merged.next;
        }
        if (list1==null){
            merged.next=list2;
        }else {
            merged.next=list1;
        }

        return dummy.next;
    }
    public ListNode mergeKLists(ListNode[] lists) {

        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}
